/**
 * 最大矩阵
 *
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 *
 * 示例 1：
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 * 解释：最大矩形如上图所示。
 *
 * 示例 2：
 * 输入：matrix = [["0"]]
 * 输出：0
 *
 * 示例 3：
 * 输入：matrix = [["1"]]
 * 输出：1
 *
 * 提示：
 * rows == matrix.length
 * cols == matrix[0].length
 * 1 <= row, cols <= 200
 * matrix[i][j] 为 '0' 或 '1'
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 这一题是啥意思呢? 其实就是我们上一题的演变, 你看我们的 matrix 有多少行
 * 那我们就调用多少次 84 题, 我们只需要将每一行看成一个新的底就可以了, 上面
 * 加上这行连着的一就是我们的这行高度, 就边长 84 题了
 * 时间复杂度 : O(m * n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 全局变量
    int len;
    List<int[]> list;
    int maxArea;

    public int maximalRectangle(char[][] matrix) {

        // 初始化
        len = 0;
        list = new ArrayList<>();
        maxArea = 0;

        int m = matrix.length, n = matrix[0].length;

        // 每一行的高度数组
        int[] nums = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (matrix[i][j] == '0') {

                    // 要是 1 断了, 重头开始
                    nums[j] = 0;
                } else {

                    // 1 没断, 一直累加
                    nums[j]++;
                }
            }

            // 调用 84题 函数
            findMax(nums, 0, n - 1);
        }

        return maxArea;
    }


    private void findMax(int[] nums, int i, int j) {

        for (int k = i; k <= j; k++) {

            len = list.size();

            //  list 为空的时候直接入栈
            if (len == 0) {

                list.add(new int[]{nums[k], k});

            } else {

                // 不为空, 取出栈顶元素
                int[] arr = list.get(len - 1);

                int a = arr[0], b = arr[1];

                // 看下这个数是否符合单调栈的条件
                if (a <= nums[k]) {

                    // 符合直接入栈
                    list.add(new int[]{nums[k], k});

                } else {

                    // 不符合, 我们更新 maxArea

                    // 先出栈顶元素， 没关系， 因为我们已经在前面记录了栈顶元素
                    list.remove(len - 1);

                    int ret = 0;

                    // 注意这个时候要是栈为 空的话, 我们是取不到栈后面的边界的
                    if (!list.isEmpty()) {

                        // 不为空, 左边界要注意算
                        ret = a * (k - list.get(list.size() - 1)[1] - 1);
                    } else {

                        // 为空了， 就直接是, 我们的数组左边界
                        ret = a * (k - i);
                    }

                    // 更新 maxArea
                    maxArea = Math.max(ret, maxArea);

                    // 这里我们再处理下保持这个数下面一次还要用
                    k--;

                }
            }
        }

        // 栈中还有元素
        len = list.size();
        while (len > 1) {

            // 记录栈顶元素
            int[] arr = list.get(len - 1);
            int a = arr[0], b = arr[1];

            // 因为我们保持了栈中最后还会剩下一个元素， 所以直接用, 不会越界

            // 左边界一样, 右边界一直是数组的最右边
            int ret = a * (j - list.get(len - 2)[1]);

            // 更新 maxArea
            maxArea = Math.max(maxArea, ret);

            // 移除
            list.remove(len - 1);
            len--;

        }

        // 最后一个数的边界是整个数组长度
        maxArea = Math.max(maxArea, list.get(0)[0] * (j - i + 1));
        list.remove(0);
    }
}